package com.test.daily.leetcode.y2022.m06.day0607.v01;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/7 下午 05:32
 * @version: 1.0
 */
public class Solution {
    // N个位置
    // start, 从start开始
    // aim, 目标位置
    // K, 可以走K步
    public static int way1(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        return process1(0, K, aim, N);
    }

    public static int process1(int cur, int rest, int aim, int N) {
        if (rest == 0) {
            return cur == aim ? 0 : 1;
        }
        if (cur == 0) {
            return process1(1, rest + 1, aim, N);
        }
        if (cur == N) {
            return process1(N - 1, rest - 1, aim, N);
        }
        return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
    }

    public static int way2(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim > N || aim < 1 || K < 1) {
            return -1;
        }
        int[][] dp = new int[aim + 1][K + 1];
        for (int i = 0; i <= aim; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(start, K, aim, N, dp);
    }

    public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans = -1;
        if (rest == 0) {
            ans = cur == aim ? 0 : 1;
        } else if (cur == 0) {
            ans = process2(1, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = process2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = process2(cur - 1, rest - 1, aim, N, dp)
                    + process2(cur + 1, rest - 1, aim, N, dp);
        }
        return ans;
    }

    public static int way3(int N, int start, int aim, int K) {
        int[][] dp = new int[N+1][K+1];
        for(int i = 0; i <= N; i++){
            dp[i][0] = i == aim? 1: 0;
        }
        for(int rest = 1; rest <= K; rest++){
            dp[0][rest] = dp[1][rest-1];
            for (int cur = 1; cur < N; cur++) {
                dp[cur][rest] = dp[cur-1][rest-1] + dp[cur+1][rest-1];
            }
            dp[N][rest] = dp[N-1][rest-1];
        }

        return dp[start][K];
    }
}
